#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

int maxSubArray(vector<int>& nums) 
{
  int i, m, sum;
  int n = nums.size();
  for (m = sum = nums[0], i = 1; i < n; ++i) 
  {
    sum = max(sum + nums[i], nums[i]);
    m = max(m, sum);
  }
  return m;
}



int main(int argc,char *argv[])
{
  vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  int ret  = maxSubArray( nums );


  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout<<"ret:"<<ret<<endl;



  return 0;
}
